A basic assumption of ad hoc wireless networks is that there is no pre-existing network infrastructure. This means that the network nodes must establish communication routes among themselves in order to transfer information through the network. Algorithms devised for network self-assembly, clustering, and multi-hop routing include those described by K. Sohrabi, J. Gao, V. Ailawadhi, and G. Pottie in, “A Self-Organizing Sensor Network,” Proc. 37th Allerton Conf. On Comm., Control, and Computing, Monticello Ill., September 1999. These algorithms can for example enable arbitrarily large networks to self-assemble, and permit multi-hop routing over large geographic areas under varying conditions of node mobility.
However, commercially available communication radios that enable wireless local area networks typically support only star network configurations. In the star network configuration one node of a cluster is designated as the master node, and the other nodes in the cluster are slave nodes that communicate only with the master node. Examples of typical protocols supporting the star network configuration include the IEEE 802.11 family of protocols including the 802.11a and 802.11b protocol, Hiperlan, and Bluetooth. The 802.11b protocol also includes an “ad hoc” mode, in which there is no single master node, but in which a local network of equal peer nodes is formed; each peer node can communicate directly with all other peer nodes. The advantages of the star network protocols include relatively simple network formation, ease of management of channel access, and ease of establishing and maintaining synchronism. Moreover, the low cost of such radios and the ubiquitous software support for them over many computing platforms make them attractive for a wide variety of applications.
The typical protocols supporting the star network configuration also have a number of problems. One problem with the star configuration protocols is that they do not easily support efficient multi-hop communication. For example, as described in the Related Applications, a protocol is described in which particular nodes of a network belong to multiple clusters of the network and, as such, communicate with multiple cluster heads. Unfortunately, when using a commercial radio that implements a media access control (MAC) protocol which assumes a star topology, the radios provide communication with multiple cluster heads by time-sharing communications between the cluster heads. The time-share communication significantly reduces the communication throughput of the network.
Furthermore, and even more detrimental, is that each time a node radio switches communication between different cluster heads, the radio encounters a start-up time delay as if it is being newly joined to the network. Consequently, communication delays are very large across multi-hop networks that rely upon MACs supporting a star configuration. This situation is further aggravated when using the 802.11b ad hoc mode because radios that are too far away for reliable communication with network nodes may still interfere with other links of the network, and there is no mechanism within the protocol for resolving these types of conflicts. Thus, formation of a reliable network is problematic.
Yet another problem encountered in star network configurations is that it is difficult to maintain a common timing base (synchronism) across cluster boundaries using the star network protocols. This makes it difficult to automatically establish network position or accurately time-stamp data, as may be important in sensor network applications.
In the drawings, the same reference numbers identify identical or substantially similar elements or acts. To easily identify the discussion of any particular element or act, the most significant digit or digits in a reference number refer to the Figure number in which that element is first introduced (e.g., element 400 is first introduced and discussed with respect to FIG. 4).
The headings provided herein are for convenience only and do not necessarily affect the scope or meaning of the claimed invention.